2.1 Words

在 NLP 语境下，词的考虑范围需要包括

• punctuation。
• utterance 中的 disfluencies：fragments，filled pauses。例子：I do uh main- mainly business data processing
• capitalized and uncapitalized。

词的度量

• word types $|V|$：the number of distinct words in a corpus
• word instances $N$：the total number N of running words

使用词作为 token 单位的缺点

• 并非所有语言都使用正字法（orthographic words）
  • 汉语中的每一个汉字是一个语素（morpheme），划分语料中连续的语素为不同的词的方式多样（取决于词的定义）。例子：姚明进入总决赛。不过在汉语中直接用语素作为词是一个可行的选择。
• word types 关于语料库大小的单调递增
  • Herdan’s Law / Heaps’ Law：$|V|=k{N}^{\beta }$。$\beta \in (0,1)$ 和语料库大小、题材有关。$N$ 较小时，随着 $N$ 增大 function words 和 content words 都在逐渐出现；$N$ 较大时，随着 $N$ 增大 content words 的出现占据主导（function words 有限）。

2.2 Morphemes

本书对于 morpheme 的定义：minimal meaning-bearing unit in a language。需要区别于汉语教材中的定义：最小音义复合体。

• roots：the central morpheme of the word

• affixes：additional meaning

• inflectional morphemes（屈折语素）：不改变词性、词义，只改变语法信息（时态、数、格、人称、比较级等语法范畴）。cat-s 的 -s

• derivational morphemes（派生语素）：可能改变词性、词义，创造出新词。care-ful 的 -ful

• clitic（附着语素）：在语法上像一个词，但是在形式上附着于另一个词出现，无法单独出现。I've 的 've

morphological typology 研究词如何拆分成语素。不同语言的语素分析所聚焦的维度通常都会包括 ：

• 平均每个词构成包括的语素个数。一词一语素的这一侧称为 isolating/analytic language，一词多语素的这一侧称为 synthetic language 以及更深的 polysynthetic language
• 语素的可分程度。语素之间存在清晰边界，一个语素通常表达一个语法含义，语素之间可以像积木一样组合，这一侧称为 agglutinative language（黏着语）；语素边界模糊，语素相互融合形式上难以分割，一个语素通常对应多个语法含义，这一侧称为 fusional language（屈折语）

使用语素作为 token 单位的缺点

• 语素的难以定义性（源于语义这个概念难以定义）
• 屈折语的语素难以分割为更加基础的表意单位
• 不同语言分隔词为语素的标准不同

2.3 Unicode

Unicode 是一个大小为 4 bytes 的 character set，其为每一个 character 都分配了一个 code point。

ASCII 是 Unicode 的一个子集，大小为 1 bytes，其中 0-31 和 127 为控制字符（供 teletype 使用，属于历史遗留产物），32-126 这 95 个字符是可打印字符，包括空格（32）、数字（48-57）、大小写英文字母（65-90、97-122）、标点符号等常见符号。

• 大小写字母的 byte 标识中只有 0x20 位不同

code point 对应的是语义上的 character，并不对应 glyph，character 的视觉标识由 fonts 决定

encoding 决定了实际内存储存中的字符的二进制表示

• UTF-32：定长编码；不向 ASCII 兼容；在常用情形下储存占用是 ASCII 编码的四倍

• UTF-8：不定长编码；向 ASCII 兼容；自同步（字符之间的解码不相互依赖，任意字符的任意字节不可能成为任意其他字符的首字节）；常用字符集的分布情况：

  • the first 127 characters (ASCII) are mapped to one byte
  • most remain-ing characters in European, Middle Eastern, and African scripts map to two bytes
  • most Chinese, Japanese, and Korean characters map to three bytes
  • and rarer CJKVcharacters and emojis and some symbols map to 4 bytes.
    

• python 的 str 储存 Unicode code point（储存策略区别于编码策略），和编码解耦。编码格式的问题在 I/O 处理字节流时发生。

• C++ 的字符串部分存在编码语义。

  • 不带编码信息：std::string 为 char，std::wstring 为 wchar_t
  • 带编码信息：std::u8string 为 char8_t，std::u16string 为 char16_t，std::u32string 为 char32_t

使用字符作为 token 单位的优缺

• 容易形式化定义，具有跨语言兼容性
• 词汇表小
• 序列长度爆炸
• 语义粒度过细，单个字符通常不具备语义（但是中文可以！）：模型首先需要学会拼写才能学会组词、语义；嵌入向量需要承载的信息太少

2.4 Subword Tokenization

BPE training：以字符串（字符作为单位）为例子阐述了 BPE 的核心流程：对于 corpus 中的每一个 word（包含前置空格），按照 adjacent token pair 出现频率从高到低不断合并形成新 token

BPE encoder：利用学到的词汇条，逐条执行替换规则（这意味着 corpus 中存在的词一定会被作为一整个 token）

BPE in practice：

• 我认为现代化的 BPE 的实现不可能像如上二段描述的如此朴素。
• BPE 只是 tokenization 的一个步骤
• SuperBPE、BoundlessBPE
• tokenization visualizer。可以观察到实际上的 token 分布对于不同语言有较大差异（取决于训练时的偏重）。很多存在语素分解的英语词实际上一一整个 token 出现，这会一定程度上影响模型对于构词的理解（推测影响较小）、影响 token 消耗

2.5 Corpora

谈论语料在现实中的多样性：

• 语言种类在多个层级上的不同。（语系、语族、语支）语言、方言
• 同一句话中语言种类的切换。
• 情景（genre）
• writer（speaker）的 demographic characteristics：比如 age, gender, race, socioeconomic class
• 语言随时间的变化

因此建立 corpus dataset 时需要构建 datasheet/data statement 来指明：

• Motivation: Why was the corpus collected, by whom, and who funded it?
• Situation: When and in what situation was the text written/spoken? For example, was there a task? Was the language originally spoken conversation, edited text, social media communication, monologue vs. dialogue?
• Language variety: What language (including dialect/region) was the corpus in?
• Speaker demographics: What was, e.g., the age or gender of the text’s authors?
• Collection process: How big is the data? If it is a subsample how was it sampled? Was the data collected with consent? How was the data pre-processed, and what metadata is available?
• Annotation process: What are the annotations, what are the demographics of the annotators, how were they trained, how was the data annotated?
• Distribution: Are there copyright or other intellectual property restrictions?

2.6 Regular Expression

character disjunction：[] [^] [1-3]
counter：* + ? *? +?
anchor：^ $ \b \B
disjunction：|
precedence：()
blackslash：special \\ \* \+ etc.，special \r\t\n\f，alias \d \D \w \W \s \S
lookahead assetion：(?=) (?!)
for substitution：capture group () non-capturing group (?:)

precision：reduce false position；recall：reduce false negatives

pretokenization example：r"'s|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[ˆ\s\p{L}\p{N}]+|\s+(?!\S)|\s+"

2.7 Simple Unix Tools for Word Tokenization

没看

2.8 Rule-based Tokenization

BPE 是 data-based tokenization

没看

2.9 Minimal Edit Distance

和 embedding vector 的不同在于从形式层面比较 token 的相似性

the minimum edit distance between two strings 定义：the minimum edit distance minimum number of editing operations (operations like insertion, deletion, substitution) needed to transform one string into another.

an alignment is a correspondence between substrings of the two sequences.

最简单的最小编辑距离 Levenshtein distance，包括三种操作 insert delete substitution 且代价均为 1（同字符替换 0 代价）。变种：只包括 insert delete 且代价均为 1。

DP 可以 $\mathrm{\Theta }(mn)$ 求解，$m=\mathrm{len}(source),n=\mathrm{len}(target)$